package everydayone.orangerotting;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Date 2020/03/04
 * @author 王光浩
 * @Thinking 使用暴力法解决，每一轮都遍历最新被感染的橘子然后将这些橘子进行扩散感染，如果在某一轮扩散之后没有被感染的
 * @         橘子，则该轮减一为最小轮数，然后判断所有被感染的橘子数+空格数是否等于数组元素总个数来决定是否所有的橘子都被
 * @         感染。（所以我们需要一个数据结构保存最新感染的橘子，一个计数器来统计当前所有被感染的橘子与空格数的总和键，
 * @         最后需要一个用于感染的方法）
 * @Anaylse 时间复杂度O（2n），空间复杂度O（n）
 */
public class MyMethoOne {
	private int maxLine=0;
	private int maxColumn=0;
	private int[][] fake;
	public int orangesRotting(int[][] grid) {
		LinkedList<List<Integer>> queue=new LinkedList<>();  //保存所有新增的感染橘子数
		int number=0;   //统计所有感染橘子和空格的计数器
		int round=0;    //统计轮数的计数器
		//统计相关信息
		for(int i=0;i<grid.length;i++) {
			for(int j=0;j<grid[i].length;j++) {
				if(grid[i][j]!=1)
					number++;
				else {
					if(grid[i][j]==2) {
						List<Integer> index=new ArrayList<Integer>();
						index.add(i);index.add(j);
						queue.add(index);
					}
				}
			}
		}
		if(number==grid.length*grid[0].length)return 0;
		this.fake=grid;
		this.maxLine=grid.length;
		this.maxColumn=grid[0].length;
		//感染
		while(!queue.isEmpty()) {
			number+=rotting(queue);
			round++;
		}
		return grid.length*grid[0].length==number?round-1:-1;
	}
	/**
	 * @ 对上一轮中最新被腐败的橘子进行扩散感染。
	 * @param queue the newest oranges which is rotten
	 * @return the number of rotting orange
	 */
	private int rotting(LinkedList<List<Integer>> queue) {
		int newrotten=0;
		int size=queue.size();
		while(size!=0) {
			List<Integer> tem=queue.poll();
			int line=tem.get(0);
			int column=tem.get(1);
			List<Integer> res=null;
			if((res=rottingone(line+1,column))!=null) {
				queue.add(res);
				newrotten++;
				res=null;
			}
			if((res=rottingone(line-1,column))!=null) {
				queue.add(res);
				newrotten++;
				res=null;
			}
			if((res=rottingone(line,column+1))!=null) {
				queue.add(res);
				newrotten++;
				res=null;
			}
			if((res=rottingone(line,column-1))!=null) {
				queue.add(res);
				newrotten++;
				res=null;
			}
			size--;
		}
		return newrotten;
	}
	/**
	 * @ 判断当前元素是否越界
	 * @param line 
	 * @param column
	 * @return if not out bound return true ,or return false
	 */
	private boolean judge(int line,int column) {
		return line>=0 && line<this.maxLine && column>=0 && column<this.maxColumn;
	}
	/**
	 * @ 对单个橘子进行感染
	 * @param line
	 * @param column
	 * @return if the orange can infected return true ,or return false;
	 */
	private List<Integer> rottingone(int line,int column) {
		if(judge(line,column) && fake[line][column]==1) {
			fake[line][column]=2;
			List<Integer> tem=new ArrayList<Integer>();
			tem.add(line);tem.add(column);
			return tem;
		}
		return null;
	}
}
